/*
 * @Description: 
 * @FilePath: /undefined/Users/zhouwei/Desktop/path.c
 * @Author: Wei Zhou
 * @Github: https://github.com/zromyk
 * @Date: 2020-11-30 17:14:55
 * @LastEditors: Wei Zhou
 * @LastEditTime: 2020-12-01 11:42:06
 * @Copyright: Copyright © 2017 muyiro. All rights reserved.
 */
void Prim(Graph G, Tree T) 
{
    T.Init('Empty');
    T.Add(G.任意顶点());
    while (T.所有顶点() 不包含 G.所有顶点()) {
        T.Add(G.与已添加结点路径最短的结点());
        T.Add(G.与已添加结点路径最短的边());
    }
}

void Kruskal(Graph G, Tree T) 
{
    T.Init(G.所有顶点());
    while (T.连通分量 > 1) {
        v, u = G.剩余的边中距离最短的路径上的两个结点();
        if (T.属于不同的连通分量(v, u) == true) {
            T.Add(G.Edge[v][u]);
            T.连通分量--;
        }
    }
}

/**
 * @param G {Graph}: 有向图
 * @param sta {int}: 起点编号
 */
void Dijkstra(Graph G, int sta) 
{
    int dist[G.NodeNum()];
    int sign[G.NodeNum()];
    int path[G.NodeNum()];

    /* 初始化dist, sign, path */
	for (int i = 0; i <= G.NodeNum(); i++) {
        dist[i] = G.edge[sta][i];
        sign[i] = 0;
        path[i] = G.edge[sta][i] < _MAX_ ? sta : -1;
	}
    sign[sta] =  1;
    path[sta] = -1;

    /* 求path */
	/* 求sign[i]=False的dist[i]中的最小值对应的编号 */
    for (int i = 0; i <= G.NodeNum(); i++) {
    	if (sign[i] == 0 && dist[i] < min) {
            min = dist[i];
    		j = i;
    	}
    }
    
    /* 更新sign */
    sign[j] = 1;
    
    /* 更新dist 和 path */
    for (int i = 0; i <= G.NodeNum(); i++) {
    	if (sign[i] == 0 && dist[j] + G.Edge[j][i] +  < dist[i]) {
			dist[i] = dist[j] + G.Edge[j][i];
			path[i] = j; 
    	}
    }
}

/**
 * @param G {Graph}: 有向图
 */
void Floyd(Graph G)
{
    int A[G.NodeNum()][G.NodeNum()];

    for (int i = 0; i <= G.NodeNum(); i++) {
        for (int j = 0; j <= G.NodeNum(); j++) {
            A[i][j] = G.Edge[i][j];
        }
    }
    for (int k = 0; k <= G.NodeNum(); k++) {
        for (int i = 0; i <= G.NodeNum(); i++) {
            for (int j = 0; j <= G.NodeNum(); j++) {
                if (A[i][j] > A[i][k] + A[k][j]) {
                    A[i][j] = A[i][k] + A[k][j];
                }
            }
        }
    }
}